class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def create_tree(nums):

    def dfs(left,right):
        if left > right:
            return None
        mid = (left+right)//2
        root = TreeNode(nums[mid])

        root.left = dfs(left,mid-1)
        root.right = dfs(mid+1,right)

        return root
    return dfs(0,len(nums)-1)
def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)
if __name__=="__main__":
    nums = [1,2,3,4,5,6,7,8,9]
    root = create_tree(nums)
    preorder(root)
